import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;
import java.util.Map.Entry;

import org.junit.Test;

public class MyTest {  
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode pre=head;
        ListNode curr=pre.next;
        ListNode front=curr.next;
        while(front.next!=null){
            curr.next=pre;
            pre=curr;
            curr=front;
            front=front.next;
        }
        curr.next=pre;
        front.next=curr;
        return front;
    }

    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> hashSet=new HashSet<Integer>();
        for(int num:nums){
            if(hashSet.contains(num)){
                return true;
            }else{
                hashSet.add(num);
            }
        }
        return false;
    }

    public String reverseWords(String s) {
        StringBuffer sBuffer=new StringBuffer(s.length());
        char[] word=new char[s.length()];
        int j=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==' '){
                reverseString(word, j);
                j=0;
                sBuffer.append(Arrays.toString(word));
                sBuffer.append(' ');
            }
            word[j]=s.charAt(i);
            j++;
        }
        sBuffer.append(Arrays.toString(word));
        return sBuffer.toString();
    }

    private void reverseString(char[] s,int right) {
        int left=0;
        char temp;
        while(left<right){
            temp=s[left];
            s[left]=s[right];
            s[right]=temp;
            left++;
            right--;
        }
    }

    public int[] restoreArray(int[][] adjacentPairs) {
        int[] ans=new int[adjacentPairs.length+1];
        Hashtable<Integer,HashSet<Integer>> table=new Hashtable<Integer,HashSet<Integer>>();
        for(int[] adjacentPair:adjacentPairs){
            HashSet<Integer> hashSet=table.getOrDefault(adjacentPair[0], new HashSet<Integer>());
            hashSet.add(adjacentPair[1]);
            table.put(adjacentPair[0], hashSet);
            hashSet=table.getOrDefault(adjacentPair[1], new HashSet<Integer>());
            hashSet.add(adjacentPair[0]);
            table.put(adjacentPair[1], hashSet);
        }
        for(Entry<Integer,HashSet<Integer>> entry:table.entrySet()){
            if(entry.getValue().size()==1){
                ans[0]=entry.getKey();
                break;
            }
        }        
        for(int i=1;i<ans.length;i++){
            for(int num:table.get(ans[i-1])){
                table.get(num).remove(ans[i-1]);
                ans[i]=num;
            }
        }
        return ans;
    }

    public int getLucky(String s, int k) {
        int ans=0;
        int sum=0;
        StringBuffer sBuffer=new StringBuffer(s.length());
        for(char c:s.toCharArray()){
            sBuffer.append(String.valueOf((c-'a'+1)));
        }
        for(char c:sBuffer.toString().toCharArray()){
            ans+=c-'0';
        }
        sum=ans;
        ans=0;
        while(k>1){
            while(sum>0){
                ans+=sum%10;
                sum/=10;
            }
            sum=ans;
            ans=0;
            k--;
        }
        return sum;
    }
    public String maximumNumber(String num, int[] change) {
        StringBuffer sBuffer=new StringBuffer(num.length());
        boolean isChange=false;
        int i=0;
        for(;i<num.length();i++){
            if(num.charAt(i)-'0'<=change[num.charAt(i)-'0']){
                sBuffer.append(change[num.charAt(i)-'0']);
                isChange=true;
            }else{
                sBuffer.append(num.charAt(i));
                if(isChange){
                    i++;
                    break;
                }
            }
        }
        for(;i<num.length();i++){
            sBuffer.append(num.charAt(i));
        }
        return sBuffer.toString();
    }
    
    public int lengthOfLIS(int[] nums) {
        int[] d=new int[nums.length];
        d[0]=nums[0];
        int length=0;
        for(int i=1;i<nums.length;i++){
            if(nums[i]>d[length]){
                length++;
                d[length]=nums[i];
            }else{
                int left=0;
                int right=length;                
                while(left<=right){
                    int mid=(left+right)/2;
                    if(nums[i]<=d[mid]){
                        right=mid-1;
                    }else{
                        left=mid+1;
                    }
                }
                d[left]=nums[i];
            }
        }
        return length+1;
    }

    public int minOperations(int[] target, int[] arr) {
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<target.length;i++){
            map.put(target[i], i);
        }
        ArrayList<Integer> arrayList=new ArrayList<Integer>(arr.length);
        for(int i:arr){
            if(map.containsKey(i)){
                arrayList.add(map.get(i));
            }
        }
        int[] nums=new int[arrayList.size()];
        for(int i=0;i<nums.length;i++){
            nums[i]=arrayList.get(i);
        }
        return target.length-lengthOfLIS(nums);
        
    }
    

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    int ans=-1;
    int nodeValue;
    public int findSecondMinimumValue(TreeNode root) {
        nodeValue=root.val;
        DFS(root.left);
        DFS(root.right);
        return ans;
    }
    private void DFS(TreeNode root){
        if(root==null){
            return;
        }
        if(root.val>nodeValue){
            ans=ans==-1?root.val:Math.min(ans, root.val);
            return;
        }
        DFS(root.left);
        DFS(root.right);
    }

    public List<String> letterCombinations(String digits) {
        List<String> ans=new ArrayList<String>();
        ans.add("");
        HashMap<Character,Character[]> map=new HashMap<Character,Character[]>();
        map.put('2',new Character[]{'a','b','c'});
        map.put('3',new Character[]{'d','e','f'});
        map.put('4',new Character[]{'g','h','i'});
        map.put('5',new Character[]{'j','k','l'});
        map.put('6',new Character[]{'m','n','o'});
        map.put('7',new Character[]{'p','q','r','s'});
        map.put('8',new Character[]{'t','u','v'});
        map.put('9',new Character[]{'w','x','y','z'});
        for(char digit:digits.toCharArray()){
            int length=ans.size();
            for(int i=0;i<length;i++){
                for(char c:map.get(digit)){
                    ans.add(ans.get(i)+c);
                }
            }
            for(int i=0;i<length;i++){
                ans.remove(0);
            }
        }
        return ans;
    }

    @Test
    public void test(){
        String digits="233";
        System.out.println(letterCombinations(digits));
    }
}

